// https://leetcode.cn/problems/summary-ranges/?envType=study-plan-v2&envId=top-interview-150

// 算法思路：
// 1. 遍历数组，找到每个连续区间的起点
// 2. 扩展区间直到不连续为止
// 3. 根据区间长度生成对应格式的字符串
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

class Solution 
{
public:
    vector<string> summaryRanges(vector<int>& nums) 
    {
        int m = nums.size();
        if (m == 0) return {};
        if (m == 1) return {to_string(nums[0])};

        vector<string> ret;
        int begin = 0;
        for (int i = 1 ; i <= m ; i++)
        {
            if (i == m || nums[i] != nums[i - 1] + 1)
            {
                int len = i - begin;
                if (len == 1)
                {
                    ret.push_back(to_string(nums[begin]));
                }
                else
                {
                    string tmp;
                    tmp += to_string(nums[begin]);
                    tmp += "->";
                    tmp += to_string(nums[i - 1]);
                    ret.push_back(tmp);
                }
                begin = i;
            }
        }

        return ret;
    }
};

int main()
{
    vector<int> nums1 = {0,1,2,4,5,7}, nums2 = {0,2,3,4,6,8,9};
    Solution sol;

    vector<string> vs1 = sol.summaryRanges(nums1);
    vector<string> vs2 = sol.summaryRanges(nums2);

    for (const string& str : vs1)
        cout << str << " ";
    cout << endl;

    for (const string& str : vs2)
        cout << str << " ";
    cout << endl;

    return 0;
}